package aufgabe1;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.util.Comparator;

/**
 * 
 * @author benjamin
 */
public class BinarySearchTree<T> extends BinaryTree<T> {
	private Comparator<T> _comparator;

	public BinarySearchTree(Comparator<T> comparator) {
		_comparator = comparator;
	}

	@Override
	public void addValue(T value) {
		_root = insert(_root, value);
	}

	/**
	 * Insert a value on the right position
	 * 
	 * Method is called from addValue
	 * 
	 * Recursive method
	 * 
	 * @param root
	 *            - root/start node
	 * @param value
	 *            - value to insert
	 * @return - root node
	 */
	private Node<T> insert(Node<T> root, T value) {
		if (root == null) {
			return new Node(value);
		}
		if (_comparator.compare(value, root.getValue()) <= 0) {
			root.setChild(insert(root.getChild(LEFT), value), LEFT);
		} else {
			root.setChild(insert(root.getChild(RIGHT), value), RIGHT);
		}

		return root;
	}

	@Override
	public void delValue(T value) {
		Node<T> n = _root;
		Node<T> parent = null;
		int lastIndex = LEFT;

		/*
		 * Find node to delete
		 */
		while (n != null) {
			if (n.getValue().equals(value)) {
				/*
				 * found
				 */
				_nodes--;
				_depthUpToDate = false;

				if (n.isLeaf()) {
					/*
					 * case 1: node is leaf --> delete
					 */
					if (parent == null) {
						/*
						 * node is root;
						 */
						_root = null;
					} else {
						parent.setChild(null, lastIndex);
					}
					_leaves--;

				} else if (n.getFreeChildIndex() != -1) {
					/*
					 * case 2: node has one child
					 * 
					 * rerefernce child parent (grand-parent)
					 */
					int usedIndex = 1 - n.getFreeChildIndex();
					if (parent == null) {
						/*
						 * node is root
						 */
						_root = n.getChild(usedIndex);
					} else {
						parent.setChild(n.getChild(usedIndex), lastIndex);
					}

				} else {
					/*
					 * case 3: node has two childs
					 */
					Node replaceNode = getSuccessor(n);
					if (parent == null) {
						/*
						 * node is root
						 */
						_root = replaceNode;
					} else {
						parent.setChild(replaceNode, lastIndex);
					}
					replaceNode.setChild(n.getChild(LEFT), LEFT);
					if (n.getChild(RIGHT) != replaceNode) {
						replaceNode.setChild(n.getChild(RIGHT), RIGHT);
					}
				}

				/*
				 * restart by parent to find more values
				 */
				if (parent != null) {
					n = parent;
				}
			}

			/*
			 * decide which way (depth)
			 */
			parent = n;
			if (_comparator.compare(value, n.getValue()) <= 0) {
				n = n.getChild(LEFT);
				lastIndex = LEFT;
			} else {
				n = n.getChild(RIGHT);
				lastIndex = RIGHT;
			}
		}
	}

	/**
	 * Determine the successor of the given node
	 * 
	 * @param start
	 *            - start node
	 * @return - successor
	 */
	private Node getSuccessor(Node start) {
		/*
		 * First go right
		 */
		Node next = start.getChild(RIGHT);

		if (next.isLeaf() || (next.getChild(LEFT) == null)) {
			/*
			 * if next node is a leaf or does'nt have childs on left side, this
			 * node is successor
			 */
			return next;

		} else {
			/*
			 * Go down left and return last left node
			 */
			return getSuccessor2(next.getChild(LEFT), next);
		}
	}

	/**
	 * Return last left node and delete parent reference
	 * 
	 * This method is called from getSuccessor()
	 * 
	 * Recursive method
	 * 
	 * @param n
	 *            - start/current node
	 * @param parent
	 *            - parent node
	 * @return - last left node
	 */
	private Node getSuccessor2(Node n, Node parent) {
		if (n.getChild(LEFT) == null) {
			parent.setChild(n.getChild(RIGHT), LEFT);
			return n;
		}

		return getSuccessor2(n.getChild(LEFT), n);
	}
}
